package leetcode_500;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

import helpclass.ListNode;

/**
 *@author 周杨
 *AddTwoNumbersII_445 用链表表示两个整数  返回一个链表 表示它们相加的结果 不允许反转链表
 *describe:用栈保存结果 AC 36%
 *2018年8月20日 下午3:33:56
 */
public class AddTwoNumbersII_445 {
	public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<Integer> s1=new Stack<Integer>();
        Stack<Integer> s2=new Stack<Integer>();
        ListNode run=l1;
        while(run!=null) {
        	s1.add(run.val);
        	run=run.next;
        }
        run=l2;
        while(run!=null) {
        	s2.add(run.val);
        	run=run.next;
        }
        List<Integer>list=new ArrayList<Integer>();
        boolean flag=false;
        while(!s1.isEmpty()||!s2.isEmpty()) {
        	int now=(s1.isEmpty()?0:s1.pop())+(s2.isEmpty()?0:s2.pop())+(flag?1:0);
        	list.add(now%10);
        	flag=now>=10?true:false;
        }
        if(flag)
        	list.add(1);
        ListNode res=new ListNode(list.get(list.size()-1));
        ListNode help=res;
        for(int i=list.size()-2;i>=0;--i) {
        	help.next=new ListNode(list.get(i));
        	help=help.next;
        }
        return res;
    }
}
